package com.lee.algorithm.tree;

import com.lee.algorithm.tree.struct.TreeNode;

import static com.lee.algorithm.tree.TreeUtil.printRightEdge;

/***
 * @description Morris 遍历
 *      会改变树结构，需要还原
 * @author 博客园 @ 青石路
 * @date 2022/1/10 22:59
 */
public class MorrisTraversal {

    /**
     * morris traversal
     *      如果cur无左孩子，cur向右移动（cur=cur.right）
     *      如果cur有左孩子，找到cur左子树上最右的节点，记为 mostRight
     *          如果mostRight的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
     *          如果mostRight的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）
     * @param root
     * @author 博客园 @ 青石路
     */
    public static void morris(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                // cur 有左子树

                // 找 cur 节点的左子树上的最右子节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    // mostRight.right 指向 cur，第一次来到 cur
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // 第二次来到 cur， 还原 mostRight.right = null;
                    mostRight.right = null;
                }
            }

            // cur 无左子树，右移；第二次来到 cur，右移
            cur = cur.right;
        }
    }

    /**
     * morris 先序遍历
     *      只会遍历一次的节点，直接打印
     *      会遍历两次的节点，第一次的时候打印，第二次不打印
     * @param root
     * @author 博客园 @ 青石路
     */
    public static void morrisPre(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                // cur 有左子树

                // 找 cur 节点的左子树上的最右子节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    // 第一次来到 cur，打印 cur
                    System.out.print(cur.value + " ");
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // 第二次来到 cur，mostRight.right 进行还原，cur 不打印
                    mostRight.right = null;
                }
            } else {
                // cur 节点没有左子树，直接打印
                System.out.print(cur.value + " ");
            }

            // cur 无左子树，右移；第二次来到 cur，右移
            cur = cur.right;
        }
        System.out.println();
    }

    /**
     * morris 中序遍历
     *      只会遍历一次的节点，直接打印
     *      会遍历两次的节点，第一次的时候不打印，第二次打印
     * @param root
     * @author 博客园 @ 青石路
     */
    public static void morrisIn(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                // cur 有左子树

                // 找 cur 节点的左子树上的最右子节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    // 第一次来到 cur，不打印 cur
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // 第二次来到 cur， 还原 mostRight.right = null
                    mostRight.right = null;
                }
            }
            // cur 无左子树，直接打印；遍历两次的节点，第二次打印
            System.out.print(cur.value + " ");

            // cur 无左子树，右移；第二次来到 cur，右移
            cur = cur.right;
        }
    }

    /**
     * morris 后序遍历
     *      1、每个节点第一次被遍历到的时候，不打印
     *      2、每个节点第二次被遍历到的时候，逆序打印该节点的左子树的右边界
     *      3、逆序打印整棵树的右边界
     * @param root
     * @author 博客园 @ 青石路
     */
    public static void morrisPost(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                    printRightEdge(cur.left);
                }
            }
            cur = cur.right;
        }
        printRightEdge(root);
        System.out.println();
    }

    public static void main(String[] args) {
        TreeNode<String> root = TreeUtil.initBinaryTree();
        // morrisPre(root);
        // morrisIn(root);
        morrisPost(root);
    }
}
